package P4树形结构;

import P1线性结构.ArrayList;

import java.util.Iterator;

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> , Iterable<E> {
    private ArrayList<E> list;  //存储元素的容器

    public PriorityQueue() {
        list = new ArrayList<>();
    }

    //获取父节点的角标
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("no parent");
        }
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

    @Override
    public void offer(E element) {
        list.add(element);
        siftUp(list.size() - 1);
    }

    //上浮操作
    private void siftUp(int k) {
        while (k > 0 && list.get(k).compareTo(list.get(parent(k))) > 0) {
            list.swap(k, parent(k));
            k = parent(k);
        }
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty");
        }
        E ret = list.get(0);
        list.swap(0, list.size() - 1);
        list.remove(list.size() - 1);
        siftDown(0);
        return ret;
    }

    private void siftDown(int k) {
        while (leftChild(k) < list.size()) {
            int j = leftChild(k);
            if (j + 1 < list.size() && list.get(j + 1).compareTo(list.get(j)) > 0) {
                j = j + 1;
            }
            if (list.get(k).compareTo(list.get(j)) < 0) {
                list.swap(k, j);
                k = j;
            } else {
                break;
            }
        }
    }

    @Override
    public E element() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty");
        }
        return list.get(0);
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }
}